#include<iostream>
using namespace std;

class Solution {
public:
	//字典树
	// struct Node
	// {
	//     string _s=0;
	//     size_t _size=0;
	//     Node* _next=nullptr;
	// }
	string longestWord(vector<string>& words) {
		vector<vector<string>> s;
		s.resize(26);
		int max_size = 0;
		vector<int> count;
		count.resize(26);
		std::sort(words.begin(), words.end());
		for (auto x : words)
		{
			for (int i = 0; i<words.size(); i++)
			{
				if (s[i].size() == 0 && x.size() == 1)
				{
					s[i].push_back(x);
					count[i]++;
					if (count[i]>max_size)
						max_size = count[i];
					break;
				}
				else if (s[i].size() == 0 && x.size() > 1)
					break;
				else if (s[i][0][0] == x[0])
				{
					for (int j = 0; j<s[i].size();j++)
					{
						if (s[i][j] == string(x.begin(), x.end() - 1))
						{
							s[i].push_back(x);
							if (count[i] >= x.size())
							{
								break;
							}
							else
							{
								count[i]++;
								if (count[i] > max_size)
									max_size = count[i];
								break;
							}
						}
						
					}
					break;
				}
			}
		}
		for (int i = 0; i < count.size(); i++)
		{
			if (count[i] == max_size)
			{
				for (int j = 0; j < s[i].size(); j++)
				{
					if (s[i][j].size() == max_size)
						return s[i][j];
				}
			}
		}
		return string();
	}
};

int main()
{
	vector<string> words{
	"rac", "rs", "ra", "on", "r", "otif", "o", "onpdu", "rsf", "rs", "ot", "oti", "racy", "onpd" };
	Solution test1;
	cout<<test1.longestWord(words);
	return 0;
}
